package SortAlgorithm;

import com.alibaba.fastjson.JSON;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class 桶排序 implements ISort{

    /**
     * 先将元素放入桶中,然后对每个桶进行排序
     * 桶越多,时间复杂度越小,空间复杂度越大
     */

    @Override
    public int[] sort(int[] arr) {
        return bucketSort(arr);
    }

    public int[] bucketSort(int[] arr){
        return bucketSort(arr,5);
    }

    /**
     *
     * @param arr 传进的数组
     * @param bucketSize 每个桶中最多可放的不同元素个数 默认5个
     * @return
     */
    private int[] bucketSort(int[] arr,int bucketSize) {

        int minValue = arr[0];
        int maxValue = arr[0];
        //找到最大值和最小值
        for (int value : arr) {
            if (value < minValue) {
                minValue = value;
            } else if (value > maxValue) {
                maxValue = value;
            }
        }

        //计算桶的数量
        int bucketCount=(maxValue-minValue)/bucketSize+1;

        List<List<Integer>> lists=new ArrayList<>();
        for (int i = 0; i < bucketCount; i++) {
            lists.add(new ArrayList<>());
        }

        // 利用映射函数将数据分配到各个桶中
        for (int i = 0; i < arr.length; i++) {
            //计算桶编号
            int index = (arr[i] - minValue) / bucketSize;
            lists.get(index).add(arr[i]);//放入对应桶中
        }

        //对每个桶进行排序
        for (int i = 0; i < bucketCount; i++) {
            Collections.sort(lists.get(i));
        }

        //整合
        int index=0;
        for (int i = 0; i < bucketCount; i++) {
            List<Integer> list = lists.get(i);
            if(list.size()!=0){
                for (Integer integer : list) {
                    arr[index++]=integer;
                }
            }
        }

        return arr;
    }

    public static void main(String[] args) {
        桶排序 n=new 桶排序();
        int[] arr={4,2,3,4,5,6,1,2,4,3,5,1,5,2,5,6,1,2,5};
        int[] result = n.bucketSort(arr);
        System.out.println(JSON.toJSONString(result));
        Arrays.sort(arr);
        System.out.println(JSON.toJSONString(arr));
    }

}
